0231. 2 的幂【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 位运算技巧（最优解）
• 3. 🎯 s.2 - 计算二进制中 1 的个数
• 4. 🎯 s.3 - 循环除法
• 5. 🎯 s.4 - 字符串方法

1. 📝 题目描述

• leetcode

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false。

如果存在一个整数 x 使得 n == 2^x，则认为 n 是 2 的幂次方。

---

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

---

提示：

• -2^31 <= n <= 2^31 - 1

进阶：你能够不使用循环/递归解决此问题吗？

2. 🎯 s.1 - 位运算技巧（最优解）

js

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  // 2 的幂必须是正数，且二进制表示中只有一个 1
  // n & (n-1) 会清除 n 中最右边的 1
  // 如果 n 是 2 的幂，那么 n & (n-1) 应该等于 0
  return n > 0 && (n & (n - 1)) === 0
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$
• 算法思路：
  • 2 的幂必须是正数，且二进制表示中只有一个 1，把唯一的 1 干掉，结果必为 0。
  • n & (n-1) 会清除 n 中最右边的 1，由于只有一个 1，执行完之后二进制表示中无 1，结果必为 0。
  • 示例：
  • n = 8 (1000)，n-1 = 7 (0111)，n & (n-1) = 0000 = 0
  • n = 6 (0110)，n-1 = 5 (0101)，n & (n-1) = 0100 ≠ 0

3. 🎯 s.2 - 计算二进制中 1 的个数

js

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  if (n <= 0) return false

  let count = 0
  while (n > 0) {
    if ((n & 1) === 1) count++
    n >>= 1
  }

  return count === 1
}

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$
• 算法思路：
  • 通过位运算逐位检查，统计二进制表示中 1 的个数。
  • 2 的幂必然是正数，且二进制表示中只有一个 1。
  • 如果最终计算结果中 1 的个数不为 1，则意味着输入的数不是 2 的幂。

4. 🎯 s.3 - 循环除法

js

var isPowerOfTwo = function (n) {
  if (n <= 0) return false

  // 不断除以 2，直到不能整除为止
  while (n % 2 === 0) {
    n /= 2
  }

  // 如果最后结果是 1，说明原来是 2 的幂
  return n === 1
}

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$
• 算法思路：
  • 不断将 n 除以 2，如果最终结果是 1，则原数是 2 的幂。

5. 🎯 s.4 - 字符串方法

js

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  // 2 的幂必须是正数，且二进制表示中只有一个 1
  if (n <= 0) return false

  // 使用内置函数计算二进制中 1 的个数
  return (n.toString(2).match(/1/g) || []).length === 1
}

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(logn)$
• 算法思路：
  • 将数字转换为二进制字符串，然后统计其中 1 的个数。